﻿#include "Matrix.h"
#include <iostream>

int* multiMatrix(const int* m1, size_t ySize1, size_t xSize1, const int* m2, size_t ySize2, size_t xSize2)
{
    // m[y][x] = m[x+y*xSize]
    auto xSize = xSize2;
    auto ySize = ySize1;
    int* m = (int*)malloc(xSize * ySize * sizeof(int));
    memset(m, 0, xSize * ySize * sizeof(int));

    for (int y = 0; y < ySize; y++)
    {
        for (int x = 0; x < xSize; x++)
        {
            int sum = 0;
            for (int i = 0; i < ySize2; i++)
            {
                sum += m1[i + y * xSize1] * m2[x + i * xSize2];
            }

            m[x + y * xSize] = sum;
            //printf("m(%d,%d)=%d\n", x, y, m[x + y * xSize]);
        }
    }

    return m;
}

int* powMatrix(const int* m, size_t ySize, size_t xSize, int n)
{
    size_t matrixSize = ySize * xSize * sizeof(int);
    int* resM = (int*)malloc(matrixSize);

    int* unitM = (int*)malloc(matrixSize);
    memset(unitM, 0, matrixSize);
    for (int i = 0; i < xSize; i++)
    {
        unitM[i + i * xSize] = 1;
    }

    memcpy(resM, unitM, matrixSize);

    int* originalM = (int*)malloc(matrixSize);
    memcpy(originalM, m, matrixSize);
    int* tmpM = nullptr;

    while (n)
    {
        if (n & 1)
        {
            tmpM = multiMatrix(resM, ySize, xSize, originalM, ySize, xSize);
            memcpy(resM, tmpM, matrixSize);
            free(tmpM);
        }

        tmpM = multiMatrix(originalM, ySize, xSize, originalM, ySize, xSize);
        memcpy(originalM, tmpM, matrixSize);
        free(tmpM);
        n >>= 1;
    }

    free(unitM);
    free(originalM);
    return resM;
}
